package com.xk._02算法篇._08dynamicProgramming;

/**
 * @description: 0-1背包问题
 * @author: xu
 * @date: 2022/10/20 14:28
 */
public class Knapsack {
    public static void main(String[] args) {
        int[] values1 =  new int[]{ 10, 40, 30, 50, 35, 40, 30 };
        int[] weights1 = new int[]{ 35, 30, 60, 50, 40, 10, 25 };
        int capacity1 = 150;

        int[] values =  new int[]{ 6, 3, 5, 4, 6 };
        int[] weights = new int[]{ 2, 2, 6, 5, 4 };
        int capacity = 10;
        System.out.println(new Knapsack().maxValueExactly(values, weights, capacity));
    }

    /**
     * 动态规划 刚好装进去
     * @return 如果返回-1，代表没法刚好凑够capacity这个容量
     */
    public int maxValueExactly(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;

        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= capacity; i++) {
            dp[i] = Integer.MIN_VALUE;
        }
        for (int i = 1; i <= values.length; i++) {
            for (int j = capacity; j >= weights[i - 1]; j--) {
                dp[j] = Math.max(dp[j], values[i-1] + dp[j - weights[i - 1]]);
            }
        }
        return dp[capacity] < 0 ? -1 : dp[capacity];
    }

    // 动态规划 优化 -- 一维数组
    // 时间：O(m*n)  空间：O(m)
    public int maxValue(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;

        int[] dp = new int[capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = capacity; j >= weights[i - 1]; j--) {
                dp[j] = Math.max(dp[j], values[i-1] + dp[j - weights[i - 1]]);
            }
        }
        return dp[capacity];
    }

    // 动态规划
    // 时间：O(m*n)  空间：O(m*n)
    public int maxValue1(int[] values, int[] weights, int capacity) {
        if (values == null || values.length == 0) return 0;
        if (weights == null || weights.length == 0) return 0;
        if (values.length != weights.length || capacity <= 0) return 0;

        // dp[i][j] 表示最大承重j、有前i件物品可选时的最大总价值
        // i = [i, values.length]  j = [1, capacity]
        int[][] dp = new int[values.length + 1][capacity + 1];
        for (int i = 1; i <= values.length; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j < weights[i - 1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], values[i-1] + dp[i-1][j - weights[i - 1]]);
                }
            }
        }
        return dp[values.length][capacity];
    }
}
